Due to recent advances in technology, computer users are now able to enjoy many features that provide an improved user experience, such as playing various media and multimedia content on personal, laptop, or handheld computers, as well as cellular phones and other portable media devices. For example, most computers today are able to play compact discs (CDs) and have an internet connection capable of streaming and downloading audio and video so users can enjoy their favorite media while working on their computers. Many computers are also equipped with digital versatile disc (DVD) drives enabling users to watch movies.
In some multimedia environments, a computer has access to a computer-readable medium storing media files such as Moving Picture Experts Group audio layer-3 (MP3) files and WINDOWS MEDIA technologies audio (WMA) and video files. The computer typically organizes the media files into playlists when the media files are rendered on a computer by a media player application.
Users often desire to play back a particular set of digital media files in a random order, hopefully without repeating any of the media files, until all available tracks are played. For example, a user may use a random or shuffle playback feature for playing the tracks of a music recording album in a random order rather than the original order. The user may also use random or shuffle playback for rendering a collection of image files, such as a random photo slide show.
Traditional implementations create random or shuffle playback of music files by preparing a pre-randomization of all of the music files into a “playlist” and playing the music files in a linear order from the list. This type of traditional approach, while guaranteeing the first two randomly selected music files are consistently random with easy traversal, perform poorly when the number of available music files changes. As such, the shortcomings of the pre-randomization implemention require reshuffling or a reconstruction of a new pre-randomization list which, in its simplest implementation, results in a loss of the historical data and causes music files to be repeated before the entire list has been played once. Such an implementation could even lead to the same music file being played twice in a row.
Other conventional techniques maintain status data, such as played or unplayed, for each music file. For example, a flag may be used for each music file to indicate whether or not the item has been played before a music file with an unplayed flag is randomly selected. This use of an “already played” flag in a file's state data in this approach suffers tremendous disadvantage by requiring a CPU-intensive search to find a next music file to be played. In this implementation, typically a random location in the list is chosen and that file is checked to see if it has been played. If it has not been played, then the file is chosen and played. If it has been played, then the random selection is repeated until an unplayed item is located. It is possible to construct situations in which this random selection implementation can search infinitely and never find an unplayed item.
In yet another known implementation, a list of music files yet to be played is maintained and a music file is selected from the list as needed. This approach performs a relatively easy “one hop” random selection to find the next music file to play and allows for easy addition of new music files to be shuffled. This traditional implementation, however, requires a large initial amount of memory to track the unplayed music files. This is undesirable, especially for memory-constrained devices, because it requires an immediate static allocation of a large amount of memory space to accommodate the unplayed music file list. For large lists of music it is possible to construct a scenario where sufficient memory is not available to accommodate this initial allocation thus placing an artificial limit on the size of the playlist that can be shuffled.